package com.code.test.dance;

import java.util.Arrays;

/**
 * 有一个登录日志，每一行有登入和登出时问，请判断一下最多有多少人同时在线，最 多的在线人数维持了多长时间
 * <p>
 * https://zhuanlan.zhihu.com/p/494884208
 * https://leetcode.cn/problems/corporate-flight-bookings/description/
 * <p>
 * 1109. 航班预订统计
 * <p>
 * 这里有 n 个航班，它们分别从 1 到 n 进行编号。
 * <p>
 * 有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。
 * <p>
 * 请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。
 */
public class Hangban {

    /**
     * TODO
     *
     * @param args
     */
    public static void main(String[] args) {
        int[][] bookings = {{1, 2, 10}, {2, 3, 20}, {2, 5, 25}};
//        int[] ret = corpFlightBookings(bookings, 5);

        int[] ret = baoli(bookings, 5);
        System.out.println(Arrays.toString(ret));
    }

    /**
     * https://labuladong.github.io/zgnb/5/29/
     */
    public int[] corpFlightBookings2(int[][] bookings, int n) {
        int[] diff = new int[n];
        //初始化差分数组，然后利用bookings给差分数组指定区间赋值
        for(int[] book : bookings){
            int i = book[0]-1;
            int j = book[1]-1;
            int val = book[2];

            diff[i] += val;
            if(j+1<diff.length){
                diff[j+1] -= val;
            }
        }

        //差分数组反推原始数组

        int[] res = new int[diff.length];
        res[0] = diff[0];
        for(int i=1;i<diff.length;i++){
            res[i] = res[i-1] + diff[i];
        }
        return res;
    }

    public static int[] corpFlightBookings(int[][] bookings, int n) {
        int[] nums = new int[n];
        for (int[] booking : bookings) {
            //记录当前航班的预定数,存进 nums[i]
            nums[booking[0] - 1] += booking[2];
            if (booking[1] < n) {
                //如果航班2 还没超过总航班数,则第二个索引航班的预定数量 减掉
                nums[booking[1]] -= booking[2];
            }
        }

        for (int i = 1; i < n; i++) {
            nums[i] += nums[i - 1];
        }
        return nums;
    }

    /**
     * 暴力解法
     * https://github.com/stronglxp/learnNote/blob/main/leetcode/%E5%89%8D%E7%BC%80%E5%92%8C/1109.%E8%88%AA%E7%8F%AD%E9%A2%84%E8%AE%A2%E7%BB%9F%E8%AE%A1.md
     */
    public static int[] baoli(int[][] bookings, int n) {
        int[] ret = new int[n];
        for (int i = 0; i < bookings.length; i++) {
            /**
             * 遍历开始航班-结束航班
             * 比如 2-5：2，3，4，5
             */
            for (int j = bookings[i][0]; j <= bookings[i][1]; j++) {
                /**
                 * j-1是因为航班编号是从1开始，要j-1才能符合ret数组的下标
                 * ret[j-1] +=bookings[i][2] 代表每个航班的预定数累加
                 *
                 * 输出：[10,55,45,25,25]
                 *
                 * 其实就是每一格都累加起来
                 * 解释：
                 * 航班编号        1   2   3   4   5
                 * 预订记录 1 ：   10  10
                 * 预订记录 2 ：       20  20
                 * 预订记录 3 ：       25  25  25  25
                 * 总座位数：      10  55  45  25  25
                 * 因此，answer = [10,55,45,25,25]
                 */
                ret[j - 1] += bookings[i][2];
            }
        }
        return ret;
    }
}
